package 排序算法.交换排序;
//冒泡排序
//若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
//•若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)
//•起泡排序平均时间复杂度为O(n2)
public class Swap_Sort {
    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        sortA(a);
        //sortB(a);
    }

    private static void sortA(int[] a){
        if(a==null||a.length==0){
            return;
        }
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        int temp;
        for(int i=0;i<a.length;i++){
            for (int j=0;j<a.length-i-1;j++){
                //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了
                if(a[j]>a[j+1]){
                    //若大于后面的某个值则交换
                    temp=a[j+1];
                    a[j+1]=a[j];
                    a[j]=temp;
                }
            }
        }
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    private static void sortB(int[] a){
        if(a==null||a.length==0){
            return;
        }
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        for(int i=0;i<a.length;i++){
            for (int j=a.length-1;j>i;j--){
                //从后往前冒泡
                if(a[j-1]>a[j]){
                    //若大于后面的某个值则交换
                    swap(j-1,j,a);
                }
            }
        }
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    //与前一位交换位置
    private static void swap(int i, int j, int[] a) {
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }


}
